package top.humbleyuan.linkedlist;

import top.humbleyuan.datastructure.linkedlist.BothWayNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:44
 * @Des 扁平化多级双向链表
 * @pro 研究一下递归dfs
 */
public class LeetCode_430 {
    /**
     * 扁平化多级双向链表
     * 遇到child先插入父级
     */
    public static void main(String[] args) {
        /**
         * 数据准备
         */
        BothWayNode head1 = new BothWayNode();
        head1.val = 2;

        int[] values1 = {3,6};
        head1.formListNode(values1);

        BothWayNode head2 = new BothWayNode();
        head2.val = 7;

        int[] values2 = {5,9,8};
        head2.formListNode(values2);

        BothWayNode head3 = new BothWayNode();
        head3.val = 9;

        int[] values3 = {7,0};
        head3.formListNode(values3);

        int point1 = 1,point2 = 1;
        int index = 0;

        BothWayNode temp = head1;
        while (index < point1) {
            temp = temp.next;
            index ++;
        }
        temp.child = head2;

        temp = head2;
        index = 0;
        while (index < point2) {
            temp = temp.next;
            index ++;
        }
        temp.child = head3;

        //扁平化
        temp = head1;
        while (temp != null) {
            if(temp.child == null) {
                temp = temp.next;
                continue;
            }

            //遇到有child时往父级收缩
            BothWayNode childTemp = temp.child;
            BothWayNode child = childTemp;
            temp.child = null;
            while (childTemp.next != null) {
                childTemp = childTemp.next;
            }
            //child插入父级
            childTemp.next = temp.next;
            if(temp.next != null)
                temp.next.prev = childTemp;

            temp.next = child;
            child.prev = temp;

            temp = temp.next;
        }
    }
}
